package cc.wsyw126.java.nowcoder.interview;

/**
 * Created by Administrator on 2017/5/3.
 * 有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小)
 * 给定正整数int x，请返回一个vector，代表所求的两个数（小的在前）。保证答案存在。
 * <p>
 * 思路：
 * 取得略大的数：
 * c0 是拖尾0的个数，c1是紧邻拖尾0左方位为1的个数， p为最右边但非拖尾的0 等于 c0 + c1
 * 把位p置为1
 * 将p右方所有位置为零
 * 在右方插入c1 - 1 个1
 * <p>
 * 取得略小的数：
 * c1是拖尾1的个数， c0是紧邻拖尾1的左方一连串0的个数，p为最右边但非拖尾的1 等于c0 + c1
 * 把位p置为0
 * 将p右方所以位置清零
 * 在p的紧邻右方插入c1 + 1个1
 */
public class CloseNumber {
    public int[] getCloseNumber(int x) {
        int[] result = new int[2];
        result[0] = getBig(x);
        result[1] = getSmall(x);
        return result;
    }

    private int getSmall(int x) {
        int small = x;
        int c0 = 0, c1 = 0, p = 0;
        while ((x & 0x1) == 1) {
            x = x >> 1;
            c1++;
        }
        while ((x & 0x1) == 0) {
            x = x >> 1;
            c0++;
        }
        p = c0 + c1;
        // 位0到p位清零
        small &= (~0) << (p + 1);
        // 在p后面插入c1 + 1个1
        small |= ((1 << (c1 + 1)) - 1) << (c0 - 1);
        return small;
    }

    private int getBig(int x) {
        int big = x;
        int c0 = 0, c1 = 0, p = 0;
        while ((x & 0x1) == 0) {
            x = x >> 1;
            c0++;
        }
        while ((x & 0x1) == 1) {
            x = x >> 1;
            c1++;
        }
        p = c0 + c1;
        // 翻转最右边非拖尾0
        big |= (1 << p);
        // 将p右方的所有为清零
        big &= ~((1 << p) - 1);
        // 在右方插入(c1 - 1)个1
        big |= (1 << (c1 - 1)) - 1;
        return big;
    }


}
